package main


import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 当其中一个链表为空时，直接返回另一个链表
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	// 定义新链表的头节点和指针
	var head, tail *ListNode
	if l1.Val < l2.Val {
		head = l1
		l1 = l1.Next
	} else {
		head = l2
		l2 = l2.Next
	}
	tail = head

	// 依次将两个链表中较小的节点插入到新链表中
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			tail.Next = l1
			l1 = l1.Next
		} else {
			tail.Next = l2
			l2 = l2.Next
		}
		tail = tail.Next
	}

	// 将剩余的节点插入到新链表的末尾
	if l1 != nil {
		tail.Next = l1
	} else if l2 != nil {
		tail.Next = l2
	}

	return head
}

func main() {
	// 构造两个升序链表
	node4 := ListNode{Val: 4, Next: nil}
	node2 := ListNode{Val: 2, Next: &node4}
	node1 := ListNode{Val: 1, Next: &node2}

	node6 := ListNode{Val: 6, Next: nil}
	node5 := ListNode{Val: 5, Next: &node6}
	node3 := ListNode{Val: 3, Next: &node5}

	fmt.Println("链表 1：")
	printList(&node1)
	fmt.Println("链表 2：")
	printList(&node3)

	// 合并两个链表
	mergedList := mergeTwoLists(&node1, &node3)

	fmt.Println("合并后的链表：")
	printList(mergedList)
}

// 打印链表元素
func printList(head *ListNode) {
	curr := head
	for curr != nil {
		fmt.Print(curr.Val, " ")
		curr = curr.Next
	}
	fmt.Println()
}
